#include "graphalgorithm.h"
#include "GMatrix.h"
#include <QDebug>
#include <QList>
#include <algorithm>

#define round(x) (int)(floor(x + 0.5))
#define inf 0xffff


//数值微分法，画出以p1,p2为端点的直线段，value表示颜色
void DDA(QImage *image, const QPoint &p1, const QPoint &p2, QRgb value)
{
    int dx = p2.x()- p1.x(), dy = p2.y() - p1.y(); //计算出x和y方向上的变化量
    if(dx == 0 && dy == 0){ //dx = dy = 0 说明只是画一个点
        image->setPixel(p1, value);
        return;
    }
    if(abs(dx) >= abs(dy)){//x方向上的变化量大于y方向，主位移方向为x方向（x正方向或负方向）
        double k = (dy + 0.0) / dx;//计算x方向的变化率，+0.0以转换为浮点运算（此处dx一定不为0）
        QPoint p = dx > 0 ? p1 : p2;//找到p1, p2中x坐标较小的点
        int mx = p1.x() + p2.x() - p.x();//计算另一个点的x坐标
        double y = p.y();
        for(int x = p.x(); x <= mx; x++, y += k) //按x递增的方向进行扫描，x+1，y+k
            image->setPixel(x, round(y), value); //round(y)即四舍五入
    }
    else{//x方向上的变化量小于y方向，主位移方向为y方向（y正方向或负方向）
        double k = (dx + 0.0) / dy;//计算y方向的变化率，此处dy一定不为0
        QPoint p = dy > 0 ? p1 : p2;//找到p1, p2中y坐标较小的点
        int my = p1.y() + p2.y() - p.y();//计算另一个点的y坐标
        double x = p.x();
        for(int y = p.y(); y <= my; y++, x += k)//按y递增的方向进行扫描，y+1，x+k
            image->setPixel(round(x), y, value);
    }
}

void DDA(QImage *image, const QPointF &p1, const QPointF &p2, QRgb value)
{
    DDA(image, p1.toPoint(), p2.toPoint(), value);
}

//x, y表示正六边形起点坐标，b是边长，value表示颜色
void Polygon6(QImage *image, int x, int y, int b, GraphicInfo &GI, QRgb value)
{
    //根据起点和边长确定正六边形的每个顶点
    QPoint points[] = {QPoint(x, y), QPoint(x + b, y), QPoint(x + b + b / 2, round(y + b / 2 * sqrt(3))), QPoint(x + b, round(y + b * sqrt(3))),
                 QPoint(x, round(y + b * sqrt(3))), QPoint(x - b / 2, round(y + b / 2 * sqrt(3)))};
    //用DDA将六个点顺次连接起来，即画出正六边形
    for(int i = 0; i < 6; i++){
        DDA(image, points[i], points[(i + 1)%6], value);
        GI.points[i] = points[i];
    }
}

//画出顶点为p1,p2,p3的三角形，value表示颜色
void Polygon3(QImage *image, const QPoint &p1, const QPoint &p2, const QPoint &p3, QRgb value)
{
    //用DDA算法将三个点顺次连接起来，即画出三角形
    DDA(image, p1, p2, value);
    DDA(image, p1, p3, value);
    DDA(image, p3, p2, value);
}

//中点Bresenham算法，画出以p1,p2为端点的直线段，value表示颜色
void bshLine(QImage *image, const QPoint &p1, const QPoint &p2, QRgb value)
{
    int dx = p2.x() - p1.x(), dy = p2.y() - p1.y(), f = -1;//计算出x和y方向上的变化量,用f标记k的正负
    if(abs(dx) >= abs(dy)){//x方向上的变化量大于y方向，主位移方向为x方向（x正方向或负方向）
        double k = (dy + 0.0) / dx;//计算x方向的变化率，+0.0以转换为浮点运算（此处dx一定不为0）
        QPoint P1 = p1, P2 = p2;
        if(p1.x() > p2.x()) {P1 = p2; P2 = p1;} //找到p1, p2中x坐标较小的点
        if(k >= 0) f = 1;
        double d = 0.5 * f - k; //计算中点误差项的初始值
        for(int x = P1.x(), y = P1.y(); x < P2.x(); x++, d -= k){
            if(d * f < 0) { //d f异号时，表示取的是右上方的像素点，同时中点误差项需要加f(1或-1)
                d += f;
                y += f;
            }
            image->setPixel(x, y, value);//画点
        }
    }
    else{//主位移方向为y方向，同理
        double k = (dx + 0.0) / dy;
        QPoint P1 = p1, P2 = p2;
        if(p1.y() > p2.y()) {P1 = p2; P2 = p1;}
        if(k >= 0) f = 1;
        double d = 0.5 * f - k;
        for(int x = P1.x(), y = P1.y(); y < P2.y(); y++, d -= k){
            if(d * f < 0) {
                d += f;
                x += f;
            }
            image->setPixel(x, y, value);
        }
    }

}

//中点Bresenham算法，center表示椭圆的中心，size确定椭圆的大小（a, b）,value表示颜色
void bshEllipse(QImage *image, const QPoint &center, const QSize &size, QRgb value)
{
    for(int i = 0; i < 4; i++) drawPart(image, center, size, value, i);
}

//用中点Bresenham算法，画四分之一椭圆，part = 0，1，2，3分别表示画第一，四，三，二象限的部分
void drawPart(QImage *image, const QPoint &center, const QSize &size, QRgb value, int part)
{
    //根据是画哪个部分确定画点时坐标乘的系数i，j
    int i = -2 * (part / 2) + 1, j = -2 * (part == 1 || part == 2) + 1;
    //获取椭圆的长半轴和短半轴
    int a = size.width(), b = size.height();
    int x = 0, y = b;
    double a2 = a * a, b2 = b * b;
    double d = 2*x*b2 - y*a2+ b2 + 0.25*a2;//椭圆算法中点误差项的初值
    image->setPixel((x * i+ center.x()), (y * j+ center.y()) , value);

    //b2 * (x + 1) < a2 * (y - 0.5)表示画四分之椭圆的上半部分，这部分主位移方向是x方向
    for(; b2 * (x + 1) < a2 * (y - 0.5); d += b2 * (2 * x + 3)){
        if(d > 0){//当前d>0时 d需要比d<0时，多加a2 * (2 - 2 * y)
            d += a2 * (2 - 2 * y);
            y--;//取右下方的像素点
        }
        image->setPixel((++x) * i + center.x(), (y * j + center.y()), value);
    }

    //开始画下半部分，主位移方向为y方向
    d = (x + 0.25) * b2 + (1 - 2 * y) * a2;
    for(; y >= 0; d += (3 - 2 * y) * a2){
        if(d < 0){
            d += (2 * x + 2) * b2;
            x++;
        }
        image->setPixel((x * i + center.x()), (--y) * j + center.y(), value);
    }
}


//计算n的阶乘
int Fac(int n)
{
    if(n == 0 || n == 1) return 1;
    return n * Fac(n - 1);
}

//计算f的n次方
float Power(float f, int n)
{
    if(n == 0) return 1;
    return f * Power(f, n - 1);
}

//参数painter用来画曲线， GI对象包含了控制点、图形颜色等信息
void DrawBezier(QPainter &painter, const GraphicInfo & GI)
{
    Bezier<QPointF> *bezier = new Bezier<QPointF>;//创建一个bezier曲线对象，控制点类型为浮点型点
    int N = GI.ctrlPoint.size();//获取控制点的个数
    for(int i = 0; i < N; i++){
        bezier->appendPoint(GI.ctrlPoint[i]);//添加控制点到曲线
    }
    painter.setPen(GI.color);//设置画笔颜色
    painter.drawPath(bezier->getPainterPath());//画图

    delete bezier;//释放bezi曲线对象占用的空间

    //用白色的线， 把控制点顺次连接起来画出控制多边形的边
    painter.setPen(QColor(255, 255, 255));
    for(int i = 0; i < N - 1; i++)
        painter.drawLine(GI.ctrlPoint[i], GI.ctrlPoint[i + 1]);
}

//利用参数方程画Bezier曲线，CPoints是曲线的控制点，value表示颜色
void DrawBezier(QImage *image, const QVector<QPointF> &CPoints, QRgb value)
{
    int n = CPoints.size() - 1;//bezier曲线的阶数
    for(float t = 0; t <= 1; t += 0.001){
        float x = 0, y = 0;
        for(int i = 0; i < CPoints.size(); i++){
            int f = 1;
            for(int j = n - i + 1; j <= n; j++) f *= j;//计算(n-i+1)到n的乘积，用于计算基函数
            float B = (float)f / Fac(i) * Power(t, i) * Power(1 - t, n - i);//计算参数为t时的基函数
            x += B * CPoints[i].x();//计算曲线上参数t对应点的横坐标
            y += B * CPoints[i].y();//计算曲线上参数t对应点的纵坐标
        }
        image->setPixel(round(x), round(y), value);//画出计算出来的点
    }

    //用白色的线， 把控制点顺次连接起来画出控制多边形的边
    for(int i = 0; i < n; i++) DDA(image, CPoints[i], CPoints[i + 1], QRgb(0xffffff));
}

//参数painter用来画曲线， 参数GI对象包含了控制点、图形颜色等信息
void DrawBsp(QPainter &painter, const GraphicInfo &GI)
{
    BSpline<QPointF> *bspline = new BSpline<QPointF>;//创建一个B样条曲线的对象，控制点类型为浮点型点
    int N = GI.ctrlPoint.size();//获取控制点的个数
    for(int i = 0; i < N; i++){
        bspline->appendPoint(GI.ctrlPoint[i]);//添加控制点到曲线
    }
    painter.setPen(GI.color);//设置画笔颜色
    painter.drawPath(bspline->getPainterPath());//画图

    delete bspline;//释放B样条曲线对象占用的空间

    //用白色的线， 把控制点顺次连接起来画出控制多边形的边
    painter.setPen(QColor(255, 255, 255));
    for(int i = 0; i < N - 1; i++)
        painter.drawLine(GI.ctrlPoint[i], GI.ctrlPoint[i + 1]);
}

//利用参数方程画B样条曲线，CPoints是曲线的控制点，value表示颜色，m为B样条曲线的段数
void DrawBsp(QImage *image, const QVector<QPointF>& CPoints, QRgb value, int m)
{
    int n = CPoints.size() - m;//B样条曲线的阶数
    int n_ = Fac(n); //计算n的阶乘，用于后续计算基函数
    float *Fk = new float[n + 1]; //开辟数组存放基函数
    for(float t = 0; t <= 1; t += 0.001){
        //计算取当前t值的n+1个的基函数的值
        for(int k = 0; k <= n; k++){
            int sign = 1;//基函数每个求和项的符号
            float sum = 0;
            for(int j = 0; j <= n - k; j++, sign = -sign){
                int C = 1;
                for(int i = n - j + 2; i < n + 2; i++) C *= i;
                sum += sign * C * Power(t + n - k - j, n) / Fac(j);
            }
            Fk[k] = sum / n_;//第k个基函数存放到Fk[k]
            //qDebug() << Fk[k];
        }

        //计算当前t值下，每一段曲线上的点的坐标
        for(int i = 0; i < m; i++){//0 - m-1共m段曲线
            float x = 0, y = 0;
            for(int k = 0; k <= n; k++){
                x += Fk[k] * CPoints[i + k].x();
                y += Fk[k] * CPoints[i + k].y();
            }
            image->setPixel(round(x), round(y), value);//着色
        }
    }

    delete[] Fk;//释放存放基函数的数组
    //用白色的线， 把控制点顺次连接起来画出控制多边形的边
    for(int i = 0; i < CPoints.size() - 1; i++) DDA(image, CPoints[i], CPoints[i + 1], QRgb(0xffffff));
}

void bshCircle(QImage *image, const QPoint &center, int R, QRgb value)
{
    //画长半轴，短半轴均为R的椭圆 即半径为R的圆
    bshEllipse(image, center, QSize(R,R), value);
}

void trans(QImage *image, int Tx, int Ty, int Graph, GraphicInfo &GI)
{
    // 根据要变换的图形 确定n(要变换的点的个数)
    int n = Graph;

    GMatrix Mt(3, 3); //定义3*3变换阵
    Mt.SetTranslationThree(Tx, Ty);//构造平移阵
    for(int i = 0; i < n; i++){//循环将每个顶点作变换
        GMatrix p(1, 3), moveP(1, 3);
        p.SetoneThree(GI.points[i].x(), GI.points[i].y());//转换成其次坐标
        moveP = p * Mt;//平移变换
        GI.points[i] = QPoint(moveP.GetoneThreea(), moveP.GetoneThreeb());//从变换后的行向量中取出点坐标
    }
    switch (Graph) {//画出相应图形
    case gline: bshLine(image, GI.points[0], GI.points[1], GI.color); break;//直线
    case polygon3: Polygon3(image, GI.points[0], GI.points[1], GI.points[2], GI.color); break;//三角形
    case polygon6: for(int i = 0; i < 6; i++) DDA(image, GI.points[i], GI.points[(i + 1)%6], GI.color); break;//六边形
    default:break;
    }
}

void rotate(QImage *image, double R, const QPoint &pR, int Graph, GraphicInfo& GI)
{
    // 根据要变换的图形 确定n(要变换的点的个数)
    int n = Graph;

    GMatrix Mr(3, 3), Mt(3, 3), Mt2(3, 3);//定义3*3变换阵
    Mr.SetRotationThree(R / 180 * M_PI); //构造旋转阵//角度制转换为弧度制
    Mt.SetTranslationThree(-pR.x(), -pR.y()); //将旋转点和原点重合 平移阵
    Mt2.SetTranslationThree(pR.x(), pR.y());
    for(int i = 0; i < n; i++){//循环将每个顶点作变换
        GMatrix p(1, 3), moveP(1, 3);
        p.SetoneThree(GI.points[i].x(), GI.points[i].y());//转换成其次坐标
        moveP = p * Mt * Mr * Mt2;  //先将旋转点和原点重合，再旋转，最后移回原处
        GI.points[i] = QPoint(moveP.GetoneThreea(), moveP.GetoneThreeb());//从变换后的行向量中取出点坐标
    }
    switch (Graph) {
    case gline: bshLine(image, GI.points[0], GI.points[1], GI.color); break;
    case polygon3: Polygon3(image, GI.points[0], GI.points[1], GI.points[2], GI.color); break;
    case polygon6: for(int i = 0; i < 6; i++) DDA(image, GI.points[i], GI.points[(i + 1)%6], GI.color); break; break;
    default:break;
    }
}

void scale(QImage *image, double Sx, double Sy, int Graph, GraphicInfo& GI)
{
    // 根据要变换的图形 确定n（要变换的点的个数）
    int n = Graph;
    GMatrix Ms(3, 3);//定义3*3变换阵
    Ms.SetScaleThree(Sx, Sy);//构造缩放阵
    for(int i = 0; i < n; i++){//循环将每个顶点作变换
        GMatrix p(1, 3), moveP(1, 3);
        p.SetoneThree(GI.points[i].x(), GI.points[i].y());
        moveP = p * Ms;//缩放变换
        GI.points[i] = QPoint(moveP.GetoneThreea(), moveP.GetoneThreeb());
    }
    switch (Graph) {
    case gline: bshLine(image, GI.points[0], GI.points[1], GI.color); break;
    case polygon3: Polygon3(image, GI.points[0], GI.points[1], GI.points[2], GI.color); break;
    case polygon6: for(int i = 0; i < 6; i++) DDA(image, GI.points[i], GI.points[(i + 1)%6], GI.color); break;
    default:break;
    }
}

void task2(QImage *image, int x, int y, int u)
{
    for(int i = x; i < 500; i++){
        double xx = (i + 0.0)/u;
        image->setPixel(i, round(y + u * sin(xx) + u * sin(2 * xx)), qRgb(255, 0, 0));
    }
}

bool cmpOfPoints(const QPoint& p1, const QPoint& p2)
{
    return p1.y() == p2.y()? p1.x() < p2.x() : p1.y() < p2.y();
}

//根据两点计算直线的斜率和截距
void functionLine(int x0, int y0, int x1, int y1, double &k, double &b)
{
    if(x0 == x1){
        //两点横坐标相等，斜率、截距不存在
        b = inf;
        k = inf;
    }
    else{
        k = (double)(y1 - y0) / (x1 - x0);//斜率计算公式
        b = y1 - k * x1;//计算截距
    }
}

//计算扫描线与多边形的交点横坐标，x、y为多边形顶点横纵坐标数组，nowY为扫描线y值
void suitableX(double* x, double* y, int N, double nowY, double *suitable_x, int &n)
{
    n = 0;
    double k = 0, b = 0;
    for(int i = 0; i < N; i++){//遍历每个顶点
        int j = (i + 1) % N;//j为与顶点i相邻的下一个顶点的序号（取模保证数组不越界）
        if(nowY <= y[j] && nowY > y[i] || nowY > y[j] && nowY <= y[i]){
            //根据顶点的纵坐标，判断当前扫描线与这两点连成的条边是否有交点
            functionLine(x[i], y[i], x[j], y[j], k, b);//根据两点坐标计算该直线的斜率与截距
            if(k == inf) suitable_x[n++] = x[i];//斜率不存在的情况下，交点横坐标等于顶点横坐标
            else if(k != 0) suitable_x[n++] = (nowY - b) / k;//斜率不为0时，交点横坐标等于x = (nowY - b) / k
        }
    }
}

//points指向存储多边形顶点的顶点数组，value为填充颜色，Graph为图形序号，等于该图形的顶点数
void scanLineFill(QImage *image, const QPoint *points, QRgb value, int Graph)
{
   double x[50], y[50];//用于存储多边形顶点的横、纵坐标
   int minY = points[0].y(), maxY = points[0].y();
   for(int i = 0; i < Graph; i++){//Graph为图形序号，也等于该图形的顶点数
       x[i] = points[i].x();//将每个顶点的横、纵坐标分别存储，同时找出最大y和最小y
       y[i] = points[i].y();
       if(minY > points[i].y()) minY = points[i].y();//如果大于当前点的y，则记录当前点的y为最小
       if(maxY < points[i].y()) maxY = points[i].y();//如果小于当前点的y，则记录当前点的y为最大
   }
   int n = 0;//用于存放扫描线与多边形的交点个数
   double suitable_x[10];//用于存放扫描线与多边形的交点的横坐标
   for(int nowY = minY; nowY <= maxY; nowY++){//令扫描线从最小y遍历到最大y
        suitableX(x, y, Graph, nowY, suitable_x, n);//计算当前扫描线与多边形的交点，并存入suitable_x
        sort(suitable_x, suitable_x + n);//对所有交点的横坐标进行排序
        for(int i = 0; i < n; i += 2){
            for(int nowX = (int)suitable_x[i]; nowX < suitable_x[i + 1]; nowX++){
                //对交点两两配对，并着色
                image->setPixel(nowX, nowY, value);
            }
        }
   }

}

//对点(x, y)进行区域编码，参数rect是中心区域
int Encode(int x, int y, const QRect &rect)
{
    int code = 0;

    if(x < rect.left()) code = code | 1;//位于中心区域的左边界之外
    else if(x > rect.right()) code = code | 2;//位于中心区域的右边界之外

    //由于y轴正方向是屏幕下方，所以下边界之外的点y值大于rect.bottom
    if(y > rect.bottom()) code = code | 4;//位于中心区域的下边界之外
    else if(y < rect.top()) code = code | 8;//位于中心区域的上边界之外

    return code;
}

//直线剪裁算法，参数rect为裁剪区域，x1,y1,x2,y2为端点坐标，value为直线颜色
void CohenSutherlandClip(QImage *image, const QRect &rect, int x1, int y1, int x2, int y2, QRgb value)
{
    //先对两端点进行区域编码
    int code1 = Encode(x1, y1, rect), code2 = Encode(x2, y2, rect);

    //当两个端点的都在区域之内时，停止迭代
    while(code1 != 0 || code2 != 0){
        //code1&code2不为0时，说明两点位于区域外部的同一侧，“简弃”
        if(code1 & code2) return;

        //处理大于上界的点
        if(code1 & 8) {
            x1 += (rect.top() - y1) * (x2 - x1) / (y2 - y1);
            y1 = rect.top();
            code1 = Encode(x1, y1, rect);
        }
        else if(code2 & 8) {
            x2 += (rect.top() - y2) * (x2 - x1) / (y2 - y1);
            y2 = rect.top();
            code2 = Encode(x2, y2, rect);
        }
        //处理小于上界的点
        else if(code1 & 4) {
            x1 += (rect.bottom() - y1) * (x2 - x1) / (y2 - y1);
            y1 = rect.bottom();
            code1 = Encode(x1, y1, rect);
        }
        else if(code2 & 4) {
            x2 += (rect.bottom() - y2) * (x2 - x1) / (y2 - y1);
            y2 = rect.bottom();
            code2 = Encode(x2, y2, rect);
        }
        //处理大于有边界的点
        else if(code1 & 2) {
            y1 += (rect.right() - x1) * (y2 - y1) / (x2 - x1);
            x1 = rect.right();
            code1 = Encode(x1, y1, rect);
        }
        else if(code2 & 2) {
            y2 += (rect.right() - x2) * (y2 - y1) / (x2 - x1);
            x2 = rect.right();
            code2 = Encode(x2, y2, rect);
        }
        //处理小于左边界的点
        else if(code1 & 1) {
            y1 += (rect.left() - x1) * (y2 - y1) / (x2 - x1);
            x1 = rect.left();
            code1 = Encode(x1, y1, rect);
        }
        else if(code2 & 1) {
            y2 += (rect.left() - x2) * (y2 - y1) / (x2 - x1);
            x2 = rect.left();
            code2 = Encode(x2, y2, rect);
        }
    }

    QPoint p1, p2;//剪裁后直线的点
    p1.setX(x1), p1.setY(y1), p2.setX(x2), p2.setY(y2);

    //画出剪裁后的直线和裁剪边框
    DDA(image, p1, p2, value);
    DDA(image, rect.topLeft(), rect.topRight(), value);
    DDA(image, rect.bottomLeft(), rect.bottomRight(), value);
    DDA(image, rect.topRight(), rect.bottomRight(), value);
    DDA(image, rect.topLeft(), rect.bottomLeft(), value);
}
